package 左哥算法.ch02二分;

import org.junit.Test;

import java.util.Arrays;
import java.util.Random;

public class 找到最接近的数包含 {

    @Test
    public void test() {
//        int[] arr = {1, 3, 3, 5};
        int[] arr = {1, 3, 3, 3, 5};
//        int[] arr = {1,3,5};    //r越过l

        int n = 3;
        System.out.println(findLeft(arr, n));
//        System.out.println(findLeft(arr, n));
    }

    /**
     * todo:
     * 找到左侧最接近的数（包含这个数）
     *
     * @param arr
     * @param n
     * @return
     */
    public int findLeft(int[] arr, int n) {
        int l = 0, r = arr.length - 1;
        //寻找最后一个小于n的数
        while (l <= r) {
            int m = l + r >> 1;
            if (arr[m] < n) {
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        if (l < arr.length && arr[l] <= n) return l;
        return r;
    }

    /**
     * 找到右侧最接近的数（包含这个数）
     *
     * @param arr
     * @param n
     * @return
     */
    public int findRight(int[] arr, int n) {
        int l = 0, r = arr.length - 1;
        while (l <= r) {
            int mid = l + r >> 1;
            if (n >= arr[mid]) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        if (r >= 0 && arr[r] >= n) {
            return r;
        }
        if (l < arr.length && arr[l] >= n) {
            return l;
        }
        return -1;
    }


    @Test
    public void compareLeft() {
        int count = 1000000;
        Random r = new Random();
        while (count-- > 0) {
            int n = r.nextInt(Byte.MAX_VALUE) + 1;
            int[] arr = new int[n];
            for (int i = 0; i < arr.length; i++) {
                arr[i] = r.nextInt(Short.MAX_VALUE);
            }
            Arrays.sort(arr);
            int x = r.nextInt(Short.MAX_VALUE);
            int ans = ansLeft(arr, x);
            int find = findLeft(arr, x);
            if (ans != find) {
                System.out.println("出错了");
                System.out.println(Arrays.toString(arr));
                System.out.println(x);
                System.out.println(ans);
                System.out.println(find);
                break;
            }
        }
    }

    @Test
    public void compareRight() {
        int count = 1000_000;
        Random r = new Random();
        while (count-- > 0) {
            int n = r.nextInt(Byte.MAX_VALUE) + 1;
            int[] arr = new int[n];
            for (int i = 0; i < arr.length; i++) {
                arr[i] = r.nextInt(Short.MAX_VALUE);
            }
            Arrays.sort(arr);
            int x = r.nextInt(Short.MAX_VALUE);
            int ans = ansRight(arr, x);
            int find = findRight(arr, x);
            if (ans != find) {
                System.out.println("出错了");
                System.out.println(Arrays.toString(arr));
                System.out.println(x);
                System.out.println(ans);
                System.out.println(find);
                break;
            }
        }
    }

    //暴力解
    public int ansLeft(int[] arr, int n) {
        int res = -1;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] <= n) {
                res = i;
            }
            if (arr[i] >= n) {
                return res;
            }
        }
        return res;
    }

    //暴力解
    public int ansRight(int[] arr, int n) {
        int res = -1;
        for (int i = arr.length - 1; i >= 0; i--) {
            if (arr[i] >= n) {
                res = i;
            }
            if (arr[i] <= n) {
                return res;
            }
        }
        return res;
    }

    //找到一个数在数组中的排名
    public static int rank(int[] sort, int v) {
        int l = 0, r = sort.length - 1;
        while (l <= r) {
            int m = l + r >> 1;
            if (sort[m] < v) {  //找到第一个小于
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        if (l < sort.length && sort[l] <= v) {
            return l + 1;
        }
        if (r < 0) return 0;
        return r + 1;
    }
    //标答
    public static int rank2(int[] sort, int v) {
        int i = 0;
        for (; i < sort.length && sort[i] < v; i++) {
        }
        if (i < sort.length && sort[i] <= v) {
            return i + 1;
        }
        return i;
    }

    @Test
    public void test02() {
        int count = 10000000;
        while (count-- > 0) {
            int n = (int) (Math.random() * 20 + 1);
            int[] arr = new int[n];
            for (int i = 0; i < arr.length; i++) {
                arr[i] = (int) (Math.random() * 100);
            }
            Arrays.sort(arr);
            int v = (int) (Math.random() * 100);
            int r1 = rank(arr, v);
            int ans = rank2(arr, v);
            if (r1 != ans) {
                System.out.println("error");
            }
        }
    }
}
